package LeetCode;

import java.util.LinkedList;
import java.util.List;

public class LC_113_PathSumII {

    public static void main(String[] args) {

    }

    static class Solution {
        private List<List<Integer>> result;
        private List<Integer> l;
        private int sum;
        private int curSum = 0;

        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            result = new LinkedList<>();
            if (root != null) {
                this.sum = sum;
                l = new LinkedList<>();
                pathSum(root);
            }
            return result;
        }

        private void pathSum(TreeNode root) {
            if (root != null) {
                l.add(root.val);
                curSum += root.val;
                if (root.left == null && root.right == null && curSum == sum) {
                    List<Integer> list = new LinkedList<>();
                    list.addAll(l);
                    result.add(list);
                }
                if (root.left != null) pathSum(root.left);
                if (root.right != null) pathSum(root.right);
                curSum -= root.val;
                l.remove(l.size() - 1);
            }
        }

    }
}